package chapter02_linkedList;

/**
 * 描述：  删除倒数第k个结点
 *      要删除第k个结点，要先找到k个结点的前一个结点，如果k在链表的中间，链表的长度为n
 *      那么第n-k个结点就是要找的结点。
 *      第一次遍历，随着遍历k--，遍历完成后k = k - n，那么正向遍历|k|次即可获取倒数第k个结点结点的前一个结点
 *      注意临界情况，删除的结点的头结点时没有前一个结点，因此k==0时需要单独处理
 *
 *      其他解法：
 *          栈
 *          快慢指针（一次遍历，常数空间）
 * @author hl
 * @date 2021/1/22 10:20
 */
public class RemoveLastKthNode {
    /**
     * 快慢指针，一次遍历
     * @param head
     * @param k
     * @return
     */
    public ListNode removeLastKthNode2(ListNode head, int n){
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode first = head, second = newHead;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while(first != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return newHead.next;
    }

    /**
     * 两次遍历
     * @param head
     * @param k
     * @return
     */
    public Node removeLastKthNode3(Node head, int k){
        if (head == null || k < 1) {
            return head;
        }
        Node cur = new Node(0);
        //要删除结点的前一个结点是第n-k
        while(cur != null){
            k--;
            cur = cur.next;
        }
        //删除的结点是头结点
        if (k == 0) {
            return head.next;
        }
        cur = head;
        //向后走k个结点
        while(++k != 0){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return head;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);
        node1.next.next.next = new Node(4);
        node1.next.next.next.next = new Node(5);
        new RemoveLastKthNode().removeLastKthNode3(node1, 2);
    }

}
